package com.dmall.play.interview.chapter07;

public class Leetcode450V1 {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    '}';
        }
    }

    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (root.val > key) {
            root.left = deleteNode(root.left, key);
            return root;
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
            return root;
        } else {
            // 相等的情况
            if (root.left == null && root.right == null) {
                return null;
            } else if (root.right != null) {
                // 需要找到root的后继最小节点 successor
                TreeNode successor = successor(root);
                successor.right = deleteNode(root.right, successor.val);
                successor.left = root.left;
                root.left = root.right = null;
                return successor;
            } else {
                // 需要找到root的前驱最大节点 precursor
                TreeNode precursor = precursor(root);
                precursor.left = deleteNode(root.left, precursor.val);
                precursor.right = root.right;
                root.left = root.right = null;
                return precursor;
            }
        }
    }

    private TreeNode precursor(TreeNode node) {
        node = node.left;
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }

    private TreeNode successor(TreeNode node) {
        node = node.right;
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(3);
        root.left.left = new TreeNode(2);
        root.left.right = new TreeNode(4);
        root.right = new TreeNode(6);
        root.right.right = new TreeNode(7);
        Leetcode450V1 leetcode450 = new Leetcode450V1();
        TreeNode newRoot = leetcode450.deleteNode(root, 5);
        System.out.println(newRoot);
    }
}
